package week_2;
//1049



/**
 * 有一堆石头，用整数数组stones 表示。其中stones[i] 表示第 i 块石头的重量。
 *
 * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为x 和y，且x <= y。那么粉碎的可能结果如下：
 *
 * 如果x == y，那么两块石头都会被完全粉碎；
 * 如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
 * 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
 */
public class day02_week02 {
    //1.对组进行一次排序(从大到小)
    //2.让前两数相减
    //3.如果有余数,存入后者的位置,并执行流程:
        //3.1如果余数大于等于下一个数,则两数相减
        //3.2如果余数小于下一个数,则交换位置,并继续比较直到满足3.1后不计算并返回
/*    public int lastStoneWeightII(int[] stones) {

    }*/


    public static void main(String[] args) {
        int[] stones=new int[]{31,26,33,21,40};
        int a=lastStoneWeightII(stones);
        System.out.println(a);

    }



    static int value=-1;
    public static int lastStoneWeightII(int[] stones) {
        if (stones.length==0)return 0;
        //得到总质量
        int sum=0;
        for (int index:stones){
            sum+=index;
        }
        value=sum;

        backtrack(stones,0,0);

        return value;
    }
    private static void backtrack(int[] stones,int num2,int sum3){
        if(num2==stones.length){
           // if (value==-1||(sum3>=0&&sum3<value)){
            if (sum3>=0&&sum3<value){

                value=sum3;
            }
        }else {
            backtrack( stones, num2+1, sum3+stones[num2]);
            backtrack( stones, num2+1, sum3-stones[num2]);
        }
    }
}
